package algorithm.graph.adjacencymatrix;

import algorithm.graph.base.Edge;
import algorithm.graph.base.GraphUtil;

import java.util.stream.IntStream;

public class DisjointSetUnit {
    AdjacencyMatrixGraph graph;

    public DisjointSetUnit(AdjacencyMatrixGraph graph) {
        this.graph = graph;
    }

    public int[] build() {
        int[] disjointSetUnit = IntStream.range(0, graph.getNodeCount()).toArray();
        for (Edge edge : GraphUtil.getNonDirectedGraphEdgeList(graph)) {
            merge(disjointSetUnit, edge.from(), edge.to());
        }
        return disjointSetUnit;
    }

    private int findGroupId(int[] groupSetUnit, int i) {
        if (groupSetUnit[i] == i) {
            return i;
        } else {
            return findGroupId(groupSetUnit, groupSetUnit[i]);
        }
    }

    private void merge(int[] disjointSetUnit, int firstNodeId, int secondNodeId) {
        disjointSetUnit[secondNodeId] = findGroupId(disjointSetUnit, firstNodeId);
    }
}
